#include <iostream>
using namespace std;
#include <stack>
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

//class Solution {
//public:
//    bool isValid(string s) {
//        stack<char> st;
//        int n = s.size();
//        for (int i = 0; i < n; i++)
//        {
//            if (s[i] == '{' || s[i] == '(' || s[i] == '[')
//            {
//                char ch = s[i];
//                st.push(ch);
//            }
//            else
//            {
//                if (!st.empty())
//                {
//                    if ((s[i] == '}' && st.top() != '{') || (s[i] == ']' && st.top() != '[') || (s[i] == ')' && st.top() != '('))
//                    {
//                        return false;
//                    }
//                    st.pop();
//                }
//                else
//                {
//                    return false;
//                }
//            }
//        }
//        if (st.empty())
//        {
//            return true;
//        }
//        return false;
//    }
//};
//
//class Solution {
//public:
//    string simplifyPath(string path) {
//        int n = path.size();
//        for (int i = 0; i < n; i++)
//        {
//            if (path[i] == '/')
//                path[i] = ' ';
//        }
//        stringstream ss(path);
//        string str;
//        stack<string> str_stack;
//        while (ss >> str)
//        {
//            if (str == "..")
//            {
//                if (!str_stack.empty())
//                    str_stack.pop();
//            }
//            else if (str != ".")
//                str_stack.push(str);
//        }
//        if (str_stack.empty())
//            return "/";
//        string res;
//        while (!str_stack.empty())
//        {
//            res = "/" + str_stack.top() + res;
//            str_stack.pop();
//        }
//        return res;
//    }
//};
//
//class MinStack {
//public:
//    MinStack() {
//        this->get_min = INT_MAX;
//    }
//
//    void push(int val) {
//        this->st.push_back(val);
//        if (val < get_min)
//        {
//            this->get_min = val;
//        }
//    }
//
//    void pop() {
//        if (this->top() == get_min)
//        {
//            this->st.pop_back();
//            this->get_min = INT_MAX;
//            for (int i = 0; i < st.size(); i++)
//            {
//                if (st[i] < get_min)
//                {
//                    this->get_min = st[i];
//                }
//            }
//        }
//        else
//        {
//            this->st.pop_back();
//        }
//    }
//
//    int top() {
//        return this->st[st.size() - 1];
//    }
//
//    int getMin() {
//        return this->get_min;
//    }
//    vector<int> st;
//    int get_min;
//};

//class Solution {
//public:
//    bool hasCycle(ListNode* head) {
//        ListNode* n1 = head;
//        ListNode* n2 = head;
//        while (n2 != nullptr && n2->next != nullptr)
//        {
//            n2 = n2->next;
//            n2 = n2->next;
//            n1 = n1->next;
//            if (n2 == n1)
//            {
//                return true;
//            }
//        }
//        return false;
//    }
//};

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        for (int i = 1; i < tokens.size(); i++)
        {
            string& token = tokens[i];
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                int num2 = stk.top();
                stk.pop();
                int num1 = stk.top();
                stk.pop();
                if (tokens[i] == "+")
                {
                    stk.push(num1 + num2);
                }
                else if (tokens[i] == "-")
                {
                    stk.push(num1 - num2);
                }
                else if (tokens[i] == "*")
                {
                    stk.push(num1 * num2);
                }
                else if (tokens[i] == "/")
                {
                    stk.push(num1 / num2);
                }
            }
            else
            {
                stk.push(atoi(token.c_str()));
            }
        }
        return stk.top();
    }
};

int main()
{
    Solution s;
    vector<string> v = { "2","1","+","3","*" };
    cout << s.evalRPN(v);
    return 0;
}